﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution76
    {
        public string MinWindow2(string s, string p)//这个方法只能找到一个符合条件的
        {


            int lenp = p.Length;
            int lens = s.Length;
            string res = "";
            if (lens < lenp)
            {
                return res;
            }
            Dictionary<char, int> mapp = new Dictionary<char, int>();
            Dictionary<char, int> maps = new Dictionary<char, int>();
            for (int i = 0; i < lens; i++)
            {


                if (maps.ContainsKey(s[i]))
                {
                    maps[s[i]]++;

                }
                else
                {
                    maps[s[i]] = 1;
                }

            }
            for (int i = 0; i < lenp; i++)
            {

                if (mapp.ContainsKey(p[i]))
                {
                    mapp[p[i]]++;

                }
                else
                {
                    mapp[p[i]] = 1;
                }

            }


            if (!IsAnagrams(maps, mapp))
            {
                return res;
            }

            int left = 0;


            while (IsAnagrams(maps, mapp))
            {
                maps[s[left]]--;
                left++;

            }//找到左边界

            //回溯
            left--;
            maps[s[left]]++;
            int right = lens - 1;


            while (IsAnagrams(maps, mapp))
            {
                maps[s[right]]--;
                right--;

            }//找到右边界
            right++;
            maps[s[right]]++;
            Console.WriteLine("截取长度"+(right - left + 1));
            Console.WriteLine(left);
            Console.WriteLine(right);
            res = s.Substring(left, right - left + 1);

            return res;
        }
        public string MinWindow(string s, string p)//这个方法只能找到一个符合条件的
        {


            int lenp = p.Length;
            int lens = s.Length;
            string res = "";
            if (lens < lenp)
            {
                return res;
            }
            Dictionary<char, int> mapp = new Dictionary<char, int>();
            Dictionary<char, int> maps = new Dictionary<char, int>();
           
            for (int i = 0; i < lenp; i++)
            {

                if (mapp.ContainsKey(p[i]))
                {
                    mapp[p[i]]++;

                }
                else
                {
                    mapp[p[i]] = 1;
                }

            }

            int left = 0;
            int resL = -1;
            int resR = lens;
            
            for (int right = 0; right < lens; right++)
            {


                if (maps.ContainsKey(s[right]))
                {
                    maps[s[right]]++;

                }
                else
                {
                    maps[s[right]] = 1;
                }

                while (IsAnagrams(maps, mapp))//找到覆盖子串
                {

                    if ((right - left) < (resR - resL))
                    {
                        resR=right;
                        resL=left;//更新长度

                    }

                    //收缩左边，这个子串可能有不需要的，比如，p=ab,s=aaaabb,所以使用while，把多的a减去

                    maps[s[left]]--;
                    left++;

                }


            }

            if (resL < 0)
            {
                return res;
            }
            else
            {
                res = s.Substring(resL, resR - resL + 1);

                return res;
            }

            

            
        }
        public bool IsAnagrams(Dictionary<char, int> maps, Dictionary<char, int> mapp)
        {


            foreach (char ch in mapp.Keys)
            {
                //Console.WriteLine(ch);
                if (maps.ContainsKey(ch))
                {


                    if (maps[ch] < mapp[ch])
                    {
                        return false;
                    }

                }
                else
                {
                    return false;
                }

            }
            return true;

        }

    }

    class Program76
    {


        static void Main76(string[] args)
        {
            string s = "ADOBECODEBANC", t = "ABC";

            Solution76 solution = new Solution76();
          string res=  solution.MinWindow(s, t);
            Console.WriteLine(res);


        }
    }
}
